package com.yu.boot2;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

/**
 * @author zy
 * @date 2019-05-07 20:17
 **/
public class U552p1 {
    public static void main(String []args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        System.out.println(getCount(n));
        BigInteger count = getCount(n);
        String string = count.toString();
        if(string.length()>6){
            string = string.substring(string.length()-6);
        }
        System.out.println(string);
    }

    public static BigInteger getCount(int n){
        if(n<3) return new BigInteger("1");

        BigInteger  a = new BigInteger("1");
        BigInteger  b = new BigInteger("1");
        BigInteger c = new BigInteger("0");
        for(int i=3;i<=n;i++){
            c = a.add(b);
            a = b;
            b = c;
        }

        return c;
    }
}
